package com.zq.solution.algorithm.divideAndConquer;

import com.zq.solution.treenode.TreeNode;

import java.util.ArrayList;

/**
 * @Description 分治算法应用—二叉树的遍历
 * @Author ZQ
 * @Date 2020/12/7 15:05
 */
public class PreoderTraversal {
    /**
     * @Description 二叉树的前序遍历
     * 遍历的过程可以通过一个递推公式来表示
     * T(n) = 2T(2/n)+O(1)
     * 2T(2/n) 表示 原来的大问题变成两个原来一半的问题
     * O(1)表示 对二叉树的每个节点只操作一次。
     * 前序遍历的时间复杂度是 O(n)
     * @Author ZQ
     * @Date 2020/12/7 15:04
     */
    public static ArrayList<Integer> TreeTraversal(TreeNode<Integer> root){
        ArrayList<Integer> list = new ArrayList<>();
        if (root == null) return null;//退出条件
        //分：左子树与右子数
        ArrayList<Integer> left = TreeTraversal(root.left);
        ArrayList<Integer> right = TreeTraversal(root.right);

        /*前序遍历*/
//        list.add(root.val);
//        list.addAll(left);
//        list.addAll(right);
        /*中序遍历*/
//        list.addAll(left);
//        list.add(root.val);
//        list.addAll(right);
        /*后序遍历*/
        list.addAll(left);
        list.addAll(right);
        list.add(root.val);
        return list;
    }
}
